package com.uhu.code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 49. 字母异位词分组
 * https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution49 {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0, j = strs.length - 1; i <= j; i++, j--) {
            if (i != j) {
                groupStr(strs[i], map);
                groupStr(strs[j], map);
            } else {
                groupStr(strs[i], map);
            }
        }
        List<List<String>> result = new ArrayList<>();
        for (List<String> strList : map.values()) {
            result.add(strList);
        }
        return result;
    }

    private static void groupStr(String str, Map<String, List<String>> map) {
        String sortStr = getSortStr(str);
        List<String> groupStr = map.get(sortStr);
        if (groupStr != null) {
            groupStr.add(str);
            map.put(sortStr, groupStr);
        } else {
            groupStr = new ArrayList<>();
            groupStr.add(str);
            map.put(sortStr, groupStr);
        }
    }

    private static String getSortStr(String str) {
        if (str == null || str == "") {
            return "";
        }
        char[] chars = str.toCharArray();
        for (int k = 0; k < chars.length; k++) {
            for (int l = k + 1; l < chars.length; l++) {
                if (chars[k] > chars[l]) {
                    char temp = chars[k];
                    chars[k] = chars[l];
                    chars[l] = temp;
                }
            }
        }
        String sortStr = String.valueOf(chars);
        return sortStr;
    }
}
